1) Самая короткая трасса действительно самая быстрая по времени выполнения, а потому достаточно в uppaal попросить verify в настройках выдать минимальную трассу.
Нет это не обязательно, но как правило при написании модели она будет такой, что будет выполнино то, что выше.

2) Самая короткая трасса НИ В КОЕМ СЛУЧАЕ НЕ ОБЯЗАНА являться лучшей с точки зрения простоев процессоров.
    Пример:
    номер работы / время выполнения на процессоре 1 / 2
    1 100 30
    2 70 100
    
    Самое короткое (по времени работы) - это чтобы 1-й проц выполнил 2-ю работу, а 2-й - 1-ю
    Самое минимальное по простоям - это чтобы 1-й проц делал 1-ю работу, а 2-й - 2-ю
    
    Итак, - будьте бдительны
    
3) Так же пример выше показывает, почему нельзя сразу же при освобождении процесса загружать его - это сильно изменит скорость и количество комбинаций, и программа станет считаться горзадо быстрее и есть меньше памяти.
Но это не правильное решение - тут самая короткая трасса не даёт лучшего решения по простоям процессоров.
Такое решение так же не переберёт все возможные варианты исполнения.